/*************************************************************************
 * File Name:    Merge_k_Sorted_Lists.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-8 17:19:46
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Merge k Sorted Lists
 | Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
class ListNode_Cmp {
public:
    bool operator()(const ListNode *lhs, const ListNode *rhs)
    {
        return  lhs->val > rhs->val;
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, ListNode_Cmp> Q;
        
        for (size_t i = 0; i < lists.size(); ++i) {
            if (lists[i] != NULL) Q.push(lists[i]);
        }
        
        ListNode *head, *tail;
        
        head = tail = NULL;
        while (!Q.empty()) {
            if (tail == NULL) head = tail = Q.top();
            else {
                tail->next = Q.top();
                tail = tail->next;
            }
            Q.pop();
            if (tail->next != NULL) Q.push(tail->next);
        }
        if (tail != NULL) tail->next = NULL;
        return head;
    }
};
